import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        //维护s串中滑动窗口中各个字符出现次数
        HashMap<Character, Integer> hs = new HashMap<>();
        //维护t串中各个字符出现次数
        HashMap<Character, Integer> ht = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i),0)+1);
        }

        String ans = "";
        int len = Integer.MAX_VALUE;
        int cnt=0;// cnt维护的是s字符串[j,i]区间中满足t字符串的元素的个数，记录相对应字符的总数。
        //区间[j,i]表示当前滑动窗口
        for (int i = 0,j = 0; i < s.length(); i++) {

            hs.put(s.charAt(i),hs.getOrDefault(s.charAt(i),0)+1);

            //如果ht表中也包含当前字符,并且hs表中的字符个数<=ht表中的字符个数,说明该字符是必须的，并且还未到达字符串t所要求的数量
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))){
                cnt++;
            }

            //收缩滑动窗口
            //如果左边界的值不在ht表中 或者 它在hs表中的出现次数多于ht表中的出现次数
            while (j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))){
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j),count);
                j++;
            }

            //此时滑动窗口包含符串 t 的全部字符
            if(cnt == t.length() && i - j + 1 < len){
                len = i - j + 1;
                ans = s.substring(j,i+1);
            }
        }

        return ans;
    }
}